package problems.daily.y2021m6;

import utils.beans.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author habitplus
 * @since 2021-06-30 09:13
 */
public class T20210630N1 {
    // 剑指 Offer 37. 序列化二叉树

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        Queue<TreeNode> que = new LinkedList<>();
        StringBuilder builder = new StringBuilder();
        que.offer(root);

        TreeNode node;
        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; i--) {
                node = que.poll();
                if (node != null) {
                    que.offer(node.left);
                    que.offer(node.right);
                    builder.append(node.val).append(",");
                } else {
                    builder.append("null,");
                }
            }
        }
        return builder.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || "".equals(data)) {
            return null;
        }

        String[] ss = data.split(",");
        Queue<TreeNode> que = new LinkedList<>();
        TreeNode head = new TreeNode(Integer.parseInt(ss[0]));

        que.add(head);

        int k = 1;
        TreeNode tempNode, node;
        while (k < ss.length && !que.isEmpty()) {
            node = que.poll();
            if (!"null".equals(ss[k])) {
                tempNode = new TreeNode(Integer.parseInt(ss[k]));
                node.left = tempNode;
                que.offer(tempNode);
            }

            if (!"null".equals(ss[k + 1])) {
                tempNode = new TreeNode(Integer.parseInt(ss[k + 1]));
                node.right = tempNode;
                que.offer(tempNode);
            }
            k += 2;
        }
        return head;
    }


// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

    public static void main(String[] args) {
        String str = "1,2,3,null,null,4,5,";
//        String[] sss = str.split(",");
//        System.out.println();
        T20210630N1 test = new T20210630N1();
        long start = System.currentTimeMillis();
        TreeNode node = test.deserialize(str);
        String ss = test.serialize(node);
        long end = System.currentTimeMillis();
        System.out.println("共耗费的时间为：" + (end - start));
        System.out.println(ss);

    }
}
